#include "calgorithm.h"

#include <QCoreApplication>
#include <QDateTime>
#include <QDebug>

CAlgorithm::CAlgorithm(QObject *parent) :
    QObject(parent)
{
}

///
/// \brief CAlgorithm::GetPathDFS
/// 搜索路径
///
/// \param sourPoint
/// 起始点
///
/// \param destPoint
/// 终点
///
/// \param matrix
/// 迷宫矩阵
///
/// \param width
/// 迷宫的宽度
///
/// \param height
/// 迷宫的长度
///
/// \param movePath
/// 路径
///
/// \return
///
bool CAlgorithm::GetPathDFS(QPoint sourPoint, QPoint destPoint,
                         int** &matrix, int width, int height,
                         QStack < QPoint > &movePath)
{
    movePath.push(sourPoint);
    //qDebug() << sourPoint;
    if (sourPoint == destPoint)
    {// 如果找到路径 则直接返回
        return true;
    }
    else
    {
        bool flag = false;
        for (int i = 0; i < 4; i++)
        {
            QPoint curPoint = sourPoint;
            curPoint = nextPos(sourPoint, i);
            //qDebug() <<  "next: " << curPoint << endl;
            if (MazeCellState(matrix, width, height, curPoint) == eMatrixStateNone)
            {// 如果这个路径可以走 则走
                flag = true;
                MarkPoint(matrix, width, height, curPoint, i + eMatrixStateNextSouth);
                if (GetPathDFS(curPoint, destPoint, matrix, width, height, movePath))
                {
                    return true;
                }
            }
        }

        QPoint popPoint;
        popPoint = movePath.pop();
        if (MazeCellState(matrix, width, height, popPoint) != eMatrixStateObstacle)
        {// 如果这个点不是障碍物 则标记还原
            MarkPoint(matrix, width, height, popPoint, eMatrixStateNone);
        }

        if (flag == true)
        {
            return false;
        }
    }

    return false;
}

///
/// \brief CAlgorithm::curMazeCellState
/// 点的状态
///
/// \param matrix
/// \param width
/// \param height
/// \param point
/// \return
///
int CAlgorithm::MazeCellState(int **&matrix, int width, int height, QPoint point)
{
    int x = point.x();
    int y = point.y();

    if (x < 0 || x >= width || y < 0 || y >= height)
    {
        return -1;
    }
    else
    {
        return matrix[x][y];
    }
}

///
/// \brief CAlgorithm::MarkPoint
/// 标记格子的路径状态
///
/// \param point
/// 坐标
///
/// \param flag
/// 状态
///
void CAlgorithm::MarkPoint(int **&matrix, int width, int height, QPoint point, int flag)
{
    int x = point.x();
    int y = point.y();
    if (x >= width || x < 0 || y >= height || y < 0)
    {
        return ;
    }
    matrix[x][y] = flag;
}


///
/// \brief CAlgorithm::nextPos
/// 获取下一个目标的位置
///
/// \param pos
/// 当前的位置
///
/// \param di
/// 方向
///
/// \return
/// 下一个位置
///
QPoint CAlgorithm::nextPos(QPoint pos, int di)
{
    /* {行增量,列增量} */
    // 南，东，北，西
    //QPoint direc[4]={QPoint(0,1), QPoint(1,0), QPoint(0,-1), QPoint(-1,0)};

    // 南，东，北，西
    QPoint direc[4];
    direc[eMatrixStateNextSouth - eMatrixStateNextSouth] = QPoint(0, 1);
    direc[eMatrixStateNextEast - eMatrixStateNextSouth] = QPoint(1, 0);
    direc[eMatrixStateNextNorth - eMatrixStateNextSouth] = QPoint(0, -1);
    direc[eMatrixStateNextWest - eMatrixStateNextSouth] = QPoint(-1, 0);

    pos.setX(pos.x() + direc[di].x());
    pos.setY(pos.y() + direc[di].y());

    return pos;
}


///
/// \brief CAlgorithm::GetPathBFS
/// 广度优先 搜索路径
///
/// \param sourPoint
/// 起始点
///
/// \param destPoint
/// 终点
///
/// \param matrix
/// 矩阵
///
/// \param width
/// 矩阵宽度
///
/// \param height
/// 矩阵高度
///
/// \param movePath
/// 路径
///
/// \return
///
bool CAlgorithm::GetPathBFS(QPoint sourPoint, QPoint destPoint,
                          int** &matrix, int width, int height,
                          QStack < QPoint > &movePath)
{

    QQueue < BFSPathCell > path;
    BFSPathCell cell;
    bool hasPath = false;
    QPoint curPoint;
    QList < BFSPathCell > allTestCell;

    // 将第一个点入队列 起始条件
    cell.curPoint = sourPoint;
    cell.prePoint = QPoint(-1, -1);
    path.enqueue(cell);

    while (path.empty() == false)
    {
        // 当前的单元格
        cell = path.dequeue();
        //curPoint = cell.curPoint;
        allTestCell.append(cell);

        if (cell.curPoint == destPoint)
        {
            hasPath = true;
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            curPoint = nextPos(cell.curPoint, i);
            if (MazeCellState(matrix, width, height, curPoint) == eMatrixStateNone)
            {
                // 下一步的单元格
                BFSPathCell nextCell;
                MarkPoint(matrix, width, height, curPoint, i + eMatrixStateNextSouth);
                nextCell.curPoint = curPoint;
                nextCell.prePoint = cell.curPoint;
                path.enqueue(nextCell);
            }
        }
    }

    movePath.clear();
    if (hasPath == true)
    {
        movePath.append(sourPoint);
        movePath.append(destPoint);
    }

    return hasPath;

}
